package treeExercise;

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      public TreeNode(int val) {
          this.val = val;
      }
  }
public class FirstExercise {
    //判断两个二叉树是否相同
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q != null || p != null && q ==null){
            return false;
        }
        if(p == null && q == null)  return true;
        if(p.val != q.val) return false;
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
    //另一棵树的子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(isSameTree(root,subRoot)){
            return true;
        }
        if(root != null){
            if(isSubtree(root.left,subRoot)){
                return true;
            }
            if(isSubtree(root.right,subRoot)){
                return true;
            }
        }
        return false;
    }
    //翻转二叉树
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return null;
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    public int getHeight(TreeNode root){
        if(root == null) return 0;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return leftHeight > rightHeight ?
                leftHeight + 1 : rightHeight + 1;
    }

    //判断一棵二叉树是否为平衡二叉树
    public int getHeight1(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        if(leftHeight >= 0 && rightHeight >= 0 &&
                Math.abs(leftHeight - rightHeight) <= 1){
            return Math.max(leftHeight,rightHeight) + 1;
        } else {
            return -1;
        }
    }
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        return getHeight1(root) > 0;
    }
    //对称二叉树
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return isSymmetric1(root.left, root.right);
    }
    public boolean isSymmetric1(TreeNode leftRoot, TreeNode rightRoot){
        if(leftRoot == null && rightRoot != null ||
                leftRoot != null && rightRoot == null){
            return false;
        }
        if(leftRoot == null && rightRoot == null){
            return true;
        }
        if(leftRoot.val != rightRoot.val){
            return false;
        }
        return isSymmetric1(leftRoot.left,rightRoot.right) &&
                isSymmetric1(leftRoot.right,rightRoot.left);
    }
}
